package xyz.scootaloo.oj.leetcode

import org.junit.Test
import xyz.scootaloo.common.TestDsl

/**
 * @author flutterdash@qq.com
 * @since 2021/7/3 8:13
 */
class P35 : TestDsl {

    private fun searchInsert(nums: IntArray, target: Int): Int {
        if (target > nums[nums.size - 1])
            return nums.size
        if (target < nums[0])
            return 0

        var left = 0
        var right = nums.size - 1
        while (left < right) {
            val mid = left + (right - left) / 2
            val pivot = nums[mid]
            when {
                pivot == target -> {
                    return mid
                }
                pivot > target -> {
                    right = mid
                }
                else -> {
                    left = mid + 1
                }
            }
        }

        return left
    }

    @Test
    fun test0() {
        val input = intArrayOf(1, 3, 5, 6)
        searchInsert(input, 5) shouldBe 2
        searchInsert(input, 2) shouldBe 1
        searchInsert(input, 7) shouldBe 4
        searchInsert(input, 0) shouldBe 0
    }

}
